package org.tomdayu.algo.easy;

import java.util.*;

public class Main {
    public static void main(String[] args) {
//        System.out.println(isValid("{{[]}}"));

//        ListNode e1 = new ListNode(1, null);
//        ListNode e2 = new ListNode(3, null);
//        ListNode e3 = new ListNode(5, null);
//        ListNode e4 = new ListNode(7, null);
//        e1.next = e2;
//        e2.next = e3;
//        e3.next = e4;
//        ListNode f1 = new ListNode(2, null);
//        ListNode f2 = new ListNode(6, null);
//        ListNode f3 = new ListNode(7, null);
//        ListNode f4 = new ListNode(8, null);
//        f1.next = f2;
//        f2.next = f3;
//        f3.next = f4;
//        mergeTwoLists(e1, f1);

//        int[] nums = {1,1,2};
//        System.out.println(removeDuplicates(nums));

//        int[] nums = {1,2,2,7,3,4,5,6,7};
////        int[] nums = {1,2,2,1};
//        System.out.println(removeElement(nums, 1));
//
//        String haystack = "sahdbutsad", needle = "sad";
//        System.out.println(strStr(haystack, needle));
//        int[] nums = {

        System.out.println(lengthOfLastWord("fly to the mon  "));
    }

    public static boolean isValid(String s) {
        Map<Character, Character> map = new HashMap<>();
        map.put('(', ')');
        map.put('{', '}');
        map.put('[', ']');
        if (s.length() > 0 && !map.containsKey(s.charAt(0))) {//如果第一个字符不是左括号，则不符合要求，返回false
            return false;
        }
        LinkedList<Character> stack = new LinkedList<>();//用Deque或者stack也行
//        stack.addLast('!');//初始化栈，结尾判断需要，因为如果未曾
        for (char c : s.toCharArray()) {
            //利用栈
            // 思路：先进后出 最先进入的左括号应该后删除，最后进入的左括号应该先删除
            // 按照这种思路，代码应该这样写：
            // 遇到左括号入栈，栈顶的左括号要最先删除。
            // 一旦遇到不是左括号的字符，说明栈顶的左括号要出栈，这个字符应该是栈顶左括号在哈希表里的对应的右括号。如果不是，那么直接返回false
            if (map.containsKey(c)) {
                stack.addLast(c);
            }
            //栈顶的左括号准备出栈，如果不是对应的右括号，返回false；如果栈已经为空则说明左括号已经出完，而下一个却是非左括号，返回false
            else if(stack.isEmpty() || map.get(stack.removeLast()) != c) return false;
        }
        //左括号全部出完即可
        return stack.size() == 0;
    }

    /**
     *
     * @param list1
     * @param list2
     * @return
     */
    public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        //思路：创建两个指针，分别用于指向两个链表的元素。直接将参数list1和list2当作指针
        // 创建一个链表newList，不断加入比较的结果，因为list1和list2是有序的，所以移动指针依次比较元素，把较小的加入newList，它一定是两个链表中最小的值
        //直到某一个指针指向null

        ListNode head = new ListNode(0);//伪头节点
        ListNode cur = head;//创建指针指向头节点
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                cur.next = list1;
                list1 = list1.next;//谁小谁的指针后移
                cur = cur.next;//cur后移指向尾节点
            } else {
                cur.next = list2;
                list2 = list2.next;
                cur = cur.next;
            }
        }
        //将还剩下节点的链表，直接追加到新链表
        cur.next = list1 == null ? list2 : list1;
        head = head.next;
        return head;
    }

    public static int removeDuplicates(int[] nums) {
        //定义两个指针left right 比较left和right指向的元素
        //如果left != right 则将right元素放到left+1的位置
        if (nums == null || nums.length == 0) return 0;
        int left = 0;
        int right = 1;
        while (right < nums.length) {
            if (nums[left] < nums[right]) {
                nums[left+1] = nums[right];
                left++;
            }
            right++;
        }
        return left+1;
    }

    public static int removeElement(int[] nums, int val) {
        //定义两个指针left right left从左往右 right从右往左 比较left和right指向的元素
        //目标是将值为val的元素放到数组的后面，并记录重复元素个数
        //1.left往后移动，
        //如果left=val，则判断right是否等于val，如果right等于val，right--，直到找到不等于val的元素，执行left = right
        //如果left!=val，则往后寻找
        //2.需要记录重复元素的个数valCount，k等于数组长度减去valCount

        if (nums == null || nums.length == 0) return 0;
        int left = 0;//right指针指向元素的后一个位置
        int right = nums.length;//right指针指向元素的后一个位置
        int valCount = 0;
        while (left!=right) {//当left指向了right，那就是遍历完了
            if (nums[left] == val) {
                valCount++;
                //right找到一个不等于val的元素，替换left
                while (nums[--right] == val && left!=right) {
                    valCount++;
                }
                if (left==right) {//如果right=left了，结束
                    break;
                } else {//找到了nums[right]!=val的元素
                    nums[left] = nums[right];
                    left++;
                }
            } else left++;
        }
        if (nums.length == valCount) {
            nums = new int[]{};//说明全是重复的
            return 0;
        }
        return nums.length - valCount;
    }

    public static int removeElement2(int[] nums, int val) {
        //思路，遍历数组，遇到不等于val的数字，依次放左边
        int pos = 0;
        for (int num : nums) {
            if (num != val) {
                nums[pos] = num;
                pos++;
            }
        }
        return pos+1;
    }

    public static int strStr(String haystack, String needle) {
        //暴力匹配 每次拿出needle字符串相同的长度的字符串进行比较 具体来说，
        // 就是从左到右，依次获取【needle字符串长度】的字符串x，每次将字符串x的字符，依次和needle的字符比较，若完全匹配则返回

        //1.获取字符串x。x的最小下标是0，x的最大下标是haystack.length - needle.length
        for (int i = 0; i <= haystack.length() - needle.length(); i++) {
            boolean flag = true;//每次比较后是否符合的标志
            for (int j = 0; j < needle.length(); j++) {
                //2.依次比needle和x的每个字符
                if (haystack.charAt(i+j) != needle.charAt(j)) {
                    flag = false;
                    break;
                }
            }
            //一次比较后
            if (flag) return i;
        }

        return -1;
    }

    public static int kmpStr(String haystack, String needle) {
        if (haystack.length() == 0 || haystack == null || needle.length() == 0 || needle == null) {
            return -1;
        }
        //1.对needle生成部分匹配值表
        int kmp[] = new int[needle.length()];
        kmp[0] = 0;
        for (int i = 1, j = 0; i < needle.length(); i++) {
            while(j > 0 && needle.charAt(i) != needle.charAt(j)) {
                j = kmp[j-1];
            }
            if (needle.charAt(i) == needle.charAt(j)) {
                j++;
            }
            kmp[i] = j;
        }
        //2.用匹配值表进行匹配
        for (int i = 0, j = 0; i < haystack.length(); i++) {
            while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
                j = kmp[j-1];
            }
            if (haystack.charAt(i) == needle.charAt(j)) {
                j++;
            }
            if (j == needle.length()) {
                return i-j + 1;
            }
        }
        return -1;
    }


    public static int searchInsert(int[] nums, int target) {
        if (nums[nums.length-1] < target) {
            return nums.length;
        }
        //二分查找
        int left = 0;
        int right = nums.length - 1;
        //寻找第一个比target大的元素
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (target < nums[mid]){
                right = mid - 1;
            } else {
                return mid;
            }
        }
        //此时(left > right)，说明没有找到
        return nums[left] > target ? left : left+1;
    }

    public static int binarySearch(int[] arr, int left, int right, int findval) {
        //因为每次递归，若不满足条件，要么就是左指针后移要么就是右指针左移。当两个指针移动到相同的元素时候，如果依然不满足条件，那么区间未找到元素。
        //左指针后移或者右指针左移，此时，left往后或者right往前，因此left>right就是判断没有找到元素的条件。
        //如果没有找到，要求找到第一个比它大的元素
        //思路：没找到，那么一定有left=right的情况，这趟循环
//        if (left > right) return -1;
        if (left > right) {
            //找到第一个比findval大的元素，这个位置就是应插入的位置
            return arr[left] > findval ? left : left+1;
        }

        int mid = (left + right) / 2;
        if (findval > arr[mid]) {
            return binarySearch(arr, mid + 1, right, findval);
        } else if (findval < arr[mid]) {
            return binarySearch(arr, left ,mid - 1, findval);
        } else {
            return mid;
        }
    }

//    看示例 2，s = "   fly me   to   the moon  "，为了计算最后一个单词的长度，我们需要计算最后一个单词的首尾字母的下标：
//
//    单词最后一个字母的下标，也就是[最后一个非空格字符]的下标，记作 i。上例中 i 是字母 n 的下标。
//    单词第一个字母的下标，我们可以找到在 [i 左边的最近空格]的下标，记作 j，那么 j+1 就是这个单词的第一个字母的下标。如果左边没有空格，那么 j=−1。
    public static int lengthOfLastWord(String s) {
        if  (s == null || s.isEmpty()) {
            return -1;
        }

        int len = s.length()-1;
        int last = len;
        while (s.charAt(last) == ' ' && last >= 0) {
            last--;
        }

        int first = last;
        while (s.charAt(first) != ' ' && first >= 0) {
            first--;
        }
        return last - first;
    }
}

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
